package com.leet.twopoint;

public class SlideWindow {
    public String minWindow(String s, String t) {
        if(s==null || s.length()==0 || t==null || t.length()==0){
            return "";
        }
        int[] need = new int[128];
        for (int i = 0; i < t.length(); i++) {
            need[t.charAt(i)]++;
        }
        int l = 0, r = 0, size = Integer.MAX_VALUE, count = t.length(), start = 0;
        // 遍历所有字符
        while(r < s.length()){
            char c = s.charAt(r);
            if(need[c] > 0){
                count--; // 满足要求的count--;
            }
            need[c]--;//右边的字符加入窗口
            // 如果满足了,窗口中已经包含所有字符
            if(count == 0){
                // need[s.charAt(l)] < 0 满足的最小值。
                while(l < r && need[s.charAt(l)] < 0){
                    need[s.charAt(l)]++;// 释放左边移动出窗口的字符
                    // 窗口左移
                    l++;
                }
                // 记录最小的size
                if(r - l + 1 < size){
                    size = r - l + 1;
                    start = l;// 记录下最小值的开始位置
                }
                // 再移动一下就不满足了,且count要加一
                need[s.charAt(l)]++;// 释放左边移动出窗口的字符
                // 窗口左移
                l++;
                count++;
            }
            r++;
        }
        return size == Integer.MAX_VALUE ? "" : s.substring(start, start + size);
    }
}
